#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

void _quickSort(vector<int>& nums, int begin, int end)
{
	if (begin >= end)  return;
	int key = nums[rand() % (end - begin + 1) + begin];
	int left = begin - 1, right = end + 1, cur = begin;
	while (cur < right)
	{
		if (nums[cur] < key)  swap(nums[++left], nums[cur++]);
		else if (nums[cur] == key)  cur++;
		else  swap(nums[--right], nums[cur]);
	}
	_quickSort(nums, begin, left);
	_quickSort(nums, right, end);
}
void quickSort(vector<int>& nums)
{
	srand(time(nullptr));
	_quickSort(nums, 0, nums.size() - 1);
}

void _mergeSort(vector<int>& nums, int begin, int end, vector<int>& tmp)
{
	if (begin >= end)  return;
	int mid = begin + (end - begin) / 2;
	_mergeSort(nums, begin, mid, tmp);
	_mergeSort(nums, mid + 1, end, tmp);

	int cur = begin;
	int cur1 = begin, cur2 = mid + 1;
	while (cur1 <= mid || cur2 <= end)
	{
		if (cur1 <= mid && cur2 <= end)
		{
			if (nums[cur1] <= nums[cur2])
				tmp[cur++] = nums[cur1++];
			else
				tmp[cur++] = nums[cur2++];
		}
		else
		{
			while (cur1 <= mid)
				tmp[cur++] = nums[cur1++];
			while (cur2 <= end)
				tmp[cur++] = nums[cur2++];
		}
	}
	for (int i = begin; i <= end; i++)
		nums[i] = tmp[i];
}
void mergeSort(vector<int>& nums)
{
	vector<int> tmp(nums.size());
	_mergeSort(nums, 0, nums.size() - 1, tmp);
}
void adjustDown(vector<int>& nums, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && nums[child + 1] > nums[child])
			child++;
		if (nums[child] > nums[parent])  swap(nums[child], nums[parent]);
		parent = child;
		child = parent * 2 + 1;
	}
}
void heapSort(vector<int>& nums)
{
	int n = nums.size();
	for (int i = n - 1 - 1 / 2; i >= 0; i--)
	{
		adjustDown(nums, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(nums[0], nums[end]);
		end--;
		adjustDown(nums, 0, end + 1);
	}
}
int main()
{
	vector<int> nums = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	//quickSort(nums);
	//mergeSort(nums);
	heapSort(nums);
	for (auto& e : nums)  cout << e << " ";
	return 0;
}